package LinkedList;
import java.util.*;

class reverseKGroup {
    /**
     *
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        //条件 1<=k<=n
        if(head==null){
            return null;
        }
        ListNode res = new ListNode(0); //虚拟头结点
        ListNode temp = res;
        //每k个进行反转，不够k个最后的保持原顺序
        //每k个进行截断
        while(head!=null){
            ListNode curTail = head; //当前段尾
            ListNode currHead = head; //当前段头

            for(int i=0;i<k-1 && curTail!=null; i++){
                curTail = curTail.next;
            }
            //这一段不够k
            if(curTail==null){
                temp.next = currHead;
                break;
            }

            head = curTail.next; //更新下一段头
            curTail.next = null; //截断这一段链表
            ListNode reverseHead = reverse(currHead);  //逆转
            temp.next = reverseHead; //连接
            //移动temp指针
            while(temp!=null && temp.next!=null){
                temp = temp.next;
            }
        }
        return res.next;

    }

    //链表逆转
    private ListNode reverse(ListNode node){
        ListNode pre = null;
        ListNode curr = node;
        while(curr!=null){
            ListNode temp = curr.next; //保存下一个节点
            curr.next = pre;
            //两个指针往后移
            pre = curr;
            curr = temp;

        }
        return pre;
    }
}